package 动态规划.子序列.最长递增子序列;

import java.util.Arrays;

public class 最长递增子序列_300 {
    public static void main(String[] args) {
        int i = new 最长递增子序列_300().lengthOfLIS(new int[]{10, 9, 2, 5, 3, 7, 101, 18});

        System.out.println(i);

    }

    public int lengthOfLIS(int[] nums) {
        if (nums.length < 0) {
            return -1;
        }
        if (nums.length == 0) {
            return 0;
        }
        int N = nums.length;
        //dp[i]存放的是：以nums[i]结尾的最长递增子序列的长度
        int[] dp = new int[N];


        //base case：将dp[]都初始化为1
        Arrays.fill(dp, 1);

        for (int i = 0; i < N; i++) {//i=N-1就是dp[]的最后一个元素了，原为dp[]的长度和nums[]的相同
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {//找到比当前值小的，并且在当前值之前出现的值
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }

        int res = 0;
        //来遍历一次经过整理的dp[]，找出最大值
        for (int i = 0; i < dp.length; i++) {
            res = Math.max(res, dp[i]);
        }

        return res;

    }
}
